package com.formula.datastructure.exam.other;

import com.formula.datastructure.util.DataUtil;

public class MinK {
    public Integer[] minK(Integer[] array, int size) {
        int N = array.length;

        Integer[] result = new Integer[size];

        for (int i = N / 2; i >= 0; i--) {
            siftDown(array, i, N);
        }

        for (int i = 0; i < size; i++) {
            result[i] = array[0];
            array[0] = array[N - 1];
            siftDown(array, 0, N - 1);
        }

        return result;
    }

    private void siftDown(Integer[] array, int idx, int len) {
        while (getLeft(idx) < len) {
            int i = getLeft(idx);
            if (i + 1 < len && array[i] > array[i + 1]) {  // 千万记得有一个 i+1<len
                i = i + 1;
            }
            if (array[i] < array[idx]) {
                Integer temp = array[i];
                array[i] = array[idx];
                array[idx] = temp;
                idx = i;
            } else {
                break;
            }
        }
    }

    private int getLeft(int idx) {
        return 2 * idx + 1;
    }

    public static void main(String[] args) {
        MinK cal = new MinK();

        int size = 20;
        int range = 999;
        Integer[] array = DataUtil.genUniqueArray(size, range);
        DataUtil.printIndex(size);
        DataUtil.printArray(array);
        DataUtil.printArray(cal.minK(array, 8));
    }
}
